#include <stdio.h>
#include <stdlib.h>

/*数据结构的定义（也要掌握）*/
#define MAX_VEX 100
typedef enum GraphType{
    DirectedGraph,//不带权有向图
    UnDirectedGraph,//带权有向图
    DirectedNet,//不带权无向图（网）
    UnDirectedNet//带权无向图（网）
}GraphType;
typedef int VertexType;
typedef struct ArcNode{
    /*注意：一般来说，这里应该存目标顶点索引*/
    int adjVex; //目标顶点的索引
    struct ArcNode* next; //下一条弧
    int weight; //权重
}ArcNode;
typedef struct VexNode{
    VertexType data;//顶点数据
    ArcNode *firstArc;//第一条弧
}VexNode,VexList[MAX_VEX];//定义头结点列表
typedef struct {
    VexList vexList;//顶点数组，链表头结点集合
    int vexNum;//顶点个数
    int arcNum;//弧个数
    GraphType type;//图的类型
}ALGraph;//Adj-List Graph

/*邻接矩阵相关定义*/
//定义无穷大
//#define INT_MAX 999
//#define INFINITY INT
#define MAX_VEX 100
//定义弧数据类型
typedef struct ArcCell{
    int adj;//权值
    //存储其他信息
    //InfoType *info;
}ArcCell,AdjMatrix[MAX_VEX][MAX_VEX];
//定义顶点数据类型
typedef int VertexType;
//定义图数据结构，打包图的拓扑信息，包括弧信息、顶点信息、宏观信息等
typedef struct {
    AdjMatrix arcs; //弧信息
    VertexType vexs[MAX_VEX];//顶点信息，向量形式（使用索引和顶点进行映射）
    int arcNum; //弧的数量
    int vexNum;//顶点的数量
    GraphType type;//弧的类型
}MGraph;

/*BFS*/
//BFS遍历
int visit[MAX_VEX] = {0};
void BFS(ALGraph graph,VertexType v);
void BFSTraverse(ALGraph graph){
    for (int i = 1; i <= graph.vexNum; ++i) {
        VertexType v = graph.vexList[i].data;
        if (!visit[v]){
            BFS(graph,v);
            printf("\n");
        }
    }
}
void BFS(ALGraph graph,VertexType v){
    //访问源点
    visit[v] = 1;
    printf("%d ",v);
    //广度遍历要利用栈or队列
    VertexType queue[MAX_VEX] = {0};
    int head = 0,rear = 0;
    //入队第一个节点
    queue[rear++] = v;
    while(rear != head){
        VertexType src = queue[head++];
        ArcNode *arcNode = graph.vexList[src].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit[adj] == 0){
                //访问
                visit[adj] = 1;
                printf("%d ",adj);//其实应该是数组里的元素
                //入队
                queue[rear++] = adj;
            }
            arcNode = arcNode->next;
        }
    }
}

/*DFS*/
//遍历
void DFS(ALGraph graph,VertexType);
void DFSTraverse(ALGraph graph){
    for (int i = 1; i <= graph.vexNum; ++i) {
        VertexType v = graph.vexList[i].data;
        if (!visit[v]){
            DFS(graph,v);
            printf("\n");
        }
    }
}
void DFS(ALGraph graph,VertexType v){
    visit[v] = 1;
    printf("%d ",v);
    ArcNode *arcNode = graph.vexList[v].firstArc;
    while(arcNode){
        VertexType adj = arcNode->adjVex;
        if(visit[adj] == 0)
            DFS(graph,adj);
        arcNode = arcNode->next;
    }
}

//2011:打印连通分量
/*随便一种遍历就行，建议DFS*/

//2013:判断是不是根
/*只需要判断从一个定点出发的DFS遍历是否经过了全部的顶点*/
void getRoot(ALGraph graph){
    for (int i = 1; i <= graph.vexNum; ++i) {
        //遍历
        DFS(graph,i);
        //检查是否全部访问过，顺便重置访问数组
        int tag = 1;
        for (int j = 1; j < graph.vexNum; ++j) {
            if(visit[j] == 0){
                tag = 0;
            }
            visit[j] = 0;
        }
        if(tag == 1)
            printf("根：%d\n",i);
    }
}

//2014：打印u到v长度为len的简单路径
/*打印路径：需要设置全局数组变量记录访问路径；
 *控制长度：需要设置区局变量记录遍历深度（路径长度）,或者传参控制*/
VertexType path[MAX_VEX] = {0};
int pl = 0;//路径长度指针
void getU2VLen(ALGraph graph,VertexType u,VertexType v,int len){
    visit[u] = 1;
    path[pl++] = u;
    if(u == v && pl == len){//找到了
        for (int i = 0; i < pl; ++i) {
            printf("%d ",path[i]);
        }
    } else{
        ArcNode *arcNode = graph.vexList[v].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit[adj] == 0)
                //进入下一层，路径长度+1
                getU2VLen(graph,adj,v,len);
            arcNode = arcNode->next;
        }
    }
    /*回溯：删除路径中的这个节点，标记为未访问
     *原因：别的路径可能会经过该节点，构成不同长度的结果*/
    visit[u] = 0;
    pl--;
}

//2015：求距离v0最短路径为k的所有顶点
/*最短路径=>BFS；
 *控制长度：设置全局变量；
 *思路：对每个节点BFS，看看到v0的最短路径长度是不是k*/
int len = 0;
void getShortest(ALGraph graph,VertexType v,VertexType dest);
void getLenK(ALGraph graph,int k){
    for (int i = 1; i <= graph.vexNum; ++i) {
        VertexType v = graph.vexList[i].data;
        getShortest(graph,v,1);
        if(len == k){
            printf("%d\n",i);
        }
        //重置辅助变量
        len = 0;
        for (int j = 0; j < graph.vexNum; ++j) {
            visit[j] = 0;
        }
    }
}
void getShortest(ALGraph graph,VertexType v,VertexType dest){
    //访问源点
    visit[v] = 1;
    len++;
    printf("%d ",v);
    //广度遍历要利用栈or队列
    VertexType queue[MAX_VEX] = {0};
    int head = 0,rear = 0;
    //入队第一个节点
    queue[rear++] = v;
    while(rear != head){
        VertexType src = queue[head++];
        ArcNode *arcNode = graph.vexList[src].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit[adj] == 0){
                if(adj == dest) return ;//找到了直接停止搜索
                visit[adj] = 1;
                queue[rear++] = adj;
            }
            arcNode = arcNode->next;
        }
    }
}

//2016：同2011

//2017：构造逆邻接表，没什么意思

//2018：同2014

//2019：判断无向图是否连通
/*从某个顶点出发，看看能否访问其余全部顶点*/

//2020.2.2
//求两个顶点最短路径
/*BFS版本：不太好打印*/
int visit5[MAX_VEX] = {0};
void getShortestPath(ALGraph graph,VertexType s,VertexType d){
    //BFS
    visit5[s] = 1;
    int parent[MAX_VEX] = {0};
    VertexType queue[MAX_VEX] = {0};
    int head = 0,rear = 0;
    queue[rear++] = s;
    parent[s] = -1;
    while(head != rear){
        VertexType v = queue[head++];
        ArcNode *arcNode = graph.vexList[v].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit5[adj] == 0){
                parent[adj] = v;//记录上一个节点
                visit5[adj] = 1;
                queue[rear++] = adj;
                if(adj == d){//找到目标节点，顺着parent回溯路径(倒着打印)
                    printf("%d ",adj);
                    while(parent[adj] != -1){
                        printf("%d ", parent[adj]);
                        adj = parent[adj];
                    }
                    return ;
                }
            }
            arcNode = arcNode->next;
        }
    }
}
/*DFS版本：很方便*/
void getShortestPathDfs(ALGraph graph,VertexType u,VertexType v){
    visit[u] = 1;
    path[pl++] = u;
    if(u == v){//找到了
        for (int i = 0; i < pl; ++i) {
            printf("%d ",path[i]);
        }
    } else{
        ArcNode *arcNode = graph.vexList[v].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit[adj] == 0)
                getShortestPathDfs(graph,adj,v);
            arcNode = arcNode->next;
        }
    }
    /*回溯：删除路径中的这个节点，标记为未访问
     *原因：别的路径可能会经过该节点*/
    visit[u] = 0;
    pl--;
}



/*其他基础算法*/
/*判环*/
int dfsCircle(ALGraph graph,VertexType src);
int hasCircle(ALGraph graph){
    for (int i = 1; i <= graph.vexNum; ++i) {
        VertexType src = graph.vexList[i].data;
        int res = dfsCircle(graph,src);
        if(res == 1) return 1;
    }
    return 0;
}
int dfsCircle(ALGraph graph,VertexType src){
    visit[src] = 1;//标记为已访问
    ArcNode *arcNode = graph.vexList[src].firstArc;
    while(arcNode){
        /*路径上存在已经访问过的节点，则视为有环，并不一定是自己到自己，也可以是别人到别人*/
        if(visit[arcNode->adjVex] == 1)//当前节点访问过了
            return 1;
        else{//当前节点没访问过
            if(dfsCircle(graph,arcNode->adjVex))
                return 1;
        }
        arcNode = arcNode->next;
    }
    /*判断环的给关键:回溯*/
    /*目前只有连个算法要回溯：1.判环；2.求简单路径；*/
    visit[src] = 0;
    return 0;
}

/*判断连点是否连通*/
int dfsConnect(ALGraph graph,VertexType src,VertexType dest){
    visit[src] = 1;
    if(src == dest) return 1;
    ArcNode *arcNode = graph.vexList[src].firstArc;
    while(arcNode){
        VertexType adj = arcNode->adjVex;
        if(visit[adj] == 0 && dfsConnect(graph,adj,dest)==1)
            return 1;
        arcNode = arcNode->next;
    }
    return 0;
}

/*邻接表打印环*/
int pathList[MAX_VEX] = {0};
int pathLen = 0;
int visited[MAX_VEX] = {0};
//打印邻接表
void printCircle(int src){//从src开始的环
    //找到起点
    int i =  0;
    while(pathList[i] != src) i++;
    //打印环
    for (;  i< pathLen; i++) {
        printf("%d ",pathList[i]);
    }
    printf("\n");
}
//在邻接矩阵中搜索环
void DFSMG(MGraph graph,VertexType v);
void getCircleMg(MGraph graph){
    for (int i = 0; i < graph.vexNum; ++i) {
        if(visit[i] == 0){
            DFSMG(graph,i);
        }
    }
}
void DFSMG(MGraph graph,VertexType v){
    pathList[pathLen++] = v;
    if(visit[v] == 1){//找到了环
        printCircle(v);
    } else{
        visit[v] = 1;//更新状态
        for (int i = 0; i < graph.vexNum; ++i) {
            if(graph.arcs[v][i].adj != 0){//找到邻接顶点
                if(visit[i] == 0){
                    DFSMG(graph,i);//深度遍历邻接顶点
                }
            }
        }
    }
    //当前节点访问结束，回溯状态
    /*访问完v就不可能有v的环*/
    visit[v] = 2;
    pathLen -- ;
}

//2022.2.3
//找最长路径
int curPath[MAX_VEX] = {0};
int curLength = 0;
int longestPath[MAX_VEX] = {0};
int longestLength = 0;
int visit2022[MAX_VEX] = {0};
void getLongestPath(ALGraph graph,VertexType v){
    visit2022[v] = 1;
    curPath[curLength++] = v;
    if(curLength > longestLength){
        //更新最长路径
        for (int i = 0; i < curLength; ++i) {
            longestPath[i] = curPath[i];
        }
        //更新最长路径长度
        longestLength = curLength;
    }
    ArcNode *node = graph.vexList[v].firstArc;
    while(node){
        VertexType adj = node->adjVex;
        if(visit2022[adj] == 0){
            getLongestPath(graph,adj);
        }
        node = node->next;
    }

    /*回溯*/
    visit2022[v] = 0;
    curLength --;
}


/*模拟卷算法复习*/
//BFS保存最短路径
void bfs(ALGraph graph,int v,int w){
    //定义变量记录遍历状态
    int visit[MAX_VEX] = {0};
    int parent[MAX_VEX] = {0};
    VertexType queue[MAX_VEX] = {0};
    int head = 0,rear = 0;
    //开始遍历
    queue[rear++] = v;
    visit[v] = 1;
    parent[v] = -1;//源节点没有上一跳
    while(rear != head){
        VertexType vex = queue[head++];
        ArcNode *arcNode = graph.vexList[vex].firstArc;
        while(arcNode){
            VertexType adj = arcNode->adjVex;
            if(visit[adj] == 0){
                parent[adj] = vex;//标记上一跳
                visit[adj] = 1;//标记已访问
                queue[rear++] = adj;
                //判断是不是目标节点
                if(adj == w){//找到了最短路径
                    //1.通过parent数组找到路径信息
                    //2.再通过栈进行逆置
                    VertexType stack[MAX_VEX] = {0};
                    int p = 0;
                    while(adj != -1){
                        stack[p++] = adj;
                        adj = parent[adj];
                    }
                    //3.再顺序输出
                    for (int i = p-1; i >= 0; --i) {
                        printf("%d ",stack[i]);
                    }
                    return ;
                }
            }
            arcNode = arcNode->next;
        }
    }
}






int main(){


    return 0;
}